#include <mm.h>

#define NULL ((void*)0)



// Lets statically allocate the memory...
//char mem_main[MAIN_SIZE];
//char mem_bs[0]; //[BS_SIZE];


struct page_desc pages[N_PAGES];

// To keep track of what slot is free in the main memory
struct page_desc *pages_main[MAIN_PAGES];
// To keep track of what slot is free in the backing storage
struct page_desc *pages_bs[BS_PAGES];

// offsets of next free page in our 3 arrays
int next_free_main; // points to the next free slot in the main memory
int next_free_bs; // points to the next free slot in the bacing store
int next_free_page; // points to the next free page (that will not be in either
										// main memory or backing store)


// Search thru the "pages" array starting from the "next_free_page" until 
// we find another free page. When we find another free page, we set 
// "next_free_page" to that offset. If not, -1.
int find_next_free(){
  int offset;
  if(next_free_page == -1)
	  return -1;
  offset = (next_free_page + 1) % N_PAGES;
  while(offset != next_free_page){
    if(pages[offset].state == PG_FREE){
      next_free_page = offset;
      return next_free_page;
    }  
	  offset = ((offset + 1) % N_PAGES);
  }

  // If it came here, we're out of memory
  next_free_page = -1;
  return next_free_page;
}

int find_next_free_main(){
  int offset;
  if(next_free_main == -1) return -1;
  
  offset = (next_free_main + 1) % MAIN_PAGES;
  while(offset != next_free_main){
    if(pages_main[offset] == NULL){
      next_free_main = offset;
      return next_free_main;
    }  
	  offset = ((offset + 1) % MAIN_PAGES);
  }

  // If it came here, there is no free space in the main memory
  next_free_main = -1;
  return next_free_main;
}

int find_next_free_bs(){
  int offset;
  if(next_free_bs == -1) return -1;
  offset = (next_free_bs + 1) % BS_PAGES;
  while(offset != next_free_bs){
    if(pages_bs[offset] == NULL){
      next_free_bs = offset;
      return next_free_bs;
    }  
	  offset = ((offset + 1) % BS_PAGES);
  }

  // If it came here, there is no free space in the backing store
  next_free_bs = -1;
  return next_free_bs;
}


// alloc_pages tries to allocate as much page as possible (<= n_pages).
// Number of successfully allocated pages is returned in "allocated".
void alloc_pages(struct page_table *owner, int n_pages, int *allocated)
{
  struct page_desc *head, *prev, *current;
  int i;
  *allocated = 0;
  if(next_free_page == -1 || n_pages == 0) return;
  
  head = &pages[next_free_page];
  head->page_id = owner->last_page_id++;
  head->state = PG_ALLOC;
  head->owner = owner;
  head->is_kernel_page = owner->pid == 0 ? 1 : 0;
//  head->offset = next_free_page;
  *allocated = 1;
  
  prev = head;
  find_next_free();
  for(i = 1; i < n_pages && next_free_page != -1; i++){
    current = &pages[next_free_page];
    current->state = PG_ALLOC;
    current->owner = owner;
    current->page_id = owner->last_page_id++;
    current->is_kernel_page = owner->pid == 0 ? 1 : 0;
    //current->offset = next_free_page;
    prev->next = current;
    prev = current;
    *allocated += 1;
    find_next_free();
  }
  
  if(owner->tail){
    owner->tail->next = head;
    owner->tail = prev;
    owner->size += *allocated;
  } else {
    owner->head = head;
    owner->tail = prev;
    owner->size = *allocated;
  }
  
  return;
  
}



void remove_from_lru(struct page_desc *page){
	if(page == lru_list.head){
  	if((lru_list.head = page->lru_next) != NULL) lru_list.head->lru_prev = NULL;
  } else if( page == lru_list.tail) {
  	if((lru_list.tail = page->lru_prev) != NULL) lru_list.tail->lru_next = NULL;
  } else {
  	if(page->lru_next)
  		page->lru_next->lru_prev = page->lru_prev;
  	if(page->lru_prev)
  		page->lru_prev->lru_next = page->lru_next;
  }
  page->lru_prev = page->lru_next = NULL;
}

void append_to_lru(struct page_desc *page){
	if(lru_list.tail){
		page->lru_prev = lru_list.tail;
		lru_list.tail->lru_next = page;
		page->lru_next = NULL;
		lru_list.tail = page;
	} else {
		lru_list.tail = lru_list.head = page;
		page->lru_next = page->lru_prev = NULL;
	}
}

struct page_desc *pop_from_lru(){
	struct page_desc *p;
	if(lru_list.head){
		p = lru_list.head;
		if(p->lru_next){
			lru_list.head = p->lru_next;
			lru_list.head->lru_prev = NULL;
		} else {
			// Nothing in LRU
			lru_list.head = lru_list.tail = NULL;
		}
		p->lru_next = p->lru_prev = NULL;
		return p;
	} else return NULL;
}

// Reclaim (free) a page
void reset_page(struct page_desc* page){
	page->page_id = -1;
  page->state = PG_FREE;
  page->next = NULL;
  page->owner = NULL;
  page->offset = -1;
  
  // fix the links for lru list
	remove_from_lru(page);
}

void reset_page_table(struct page_table* pt){
	pt->last_page_id = 0;
  pt->pid = -1;
  pt->size = 0;
  pt->head = NULL;
  pt->tail = NULL;
}


// alloc_pt initializes a page table and allocates n_pages pages to the
// process owning that page table. If there were enough free pages,
// it returns 0, -1 otherwise.
int alloc_pt(struct page_table* pt, int pid, int n_pages){
  int allocated_pages;
  reset_page_table(pt);
  pt->pid = pid;
  pt->head = NULL;
  pt->tail = NULL;
  alloc_pages(pt, n_pages, &allocated_pages);
  return n_pages == allocated_pages ? 0 : -1;
}



void dealloc_pt(struct process* proc){
  // Iterate thru all the pages in the page table and mark them as free
  struct page_desc* p = proc->pt.head;
  struct page_desc* n = p;
  
  while(p != NULL){
  	if(p->state == PG_INMEM || p->state == PG_ALLOC){
  		pages_main[p->offset] = NULL;
  		next_free_main = p->offset;
  	} else if(p->state == PG_SWAPPED){
  		pages_bs[p->offset] = NULL;
  		next_free_bs = p->offset;
  	}
    n = p->next;
    reset_page(p);
    p = n;
  }
  
  reset_page_table(&proc->pt);
}

inline void reset_page_action(struct page_action *pa){
	pa->op = PA_NONE;
	pa->subject = NULL;
	pa->next = NULL;
	pa->source_offset = -1;
	pa->target_offset = -1;
}

int find_next_free_page_action(){
// figure out the next_free
	int offset;
	
	offset = (bs_queue.next_free + 1) % BS_Q_SIZE;
	while(offset != bs_queue.next_free){
	  if(bs_queue.page_actions[offset].op == PA_NONE){
	    bs_queue.next_free = offset;
			return offset;
		}  
		offset = (offset + 1) % BS_Q_SIZE;
	}
	bs_queue.next_free = -1;
	return bs_queue.next_free;
}

int enqueue_bs(bs_action op, struct page_desc *subject, int src_offset,
																													int tgt_offset){

	// Check if the queue is full or not
	//printf("in eq. n_el=%d\n",bs_queue.n_elements);
	if(bs_queue.n_elements == BS_Q_SIZE) return -1; // Queue full
	struct page_action *new_action = &bs_queue.page_actions[bs_queue.next_free];
	new_action->op = op;
	new_action->subject = subject;
	new_action->source_offset = src_offset;
	new_action->target_offset = tgt_offset;
	new_action->next = NULL;
	
	if(bs_queue.head) {
		bs_queue.tail->next = new_action;
		bs_queue.tail = new_action;
	} else {
		bs_queue.head = bs_queue.tail = new_action;
	}
	
	bs_queue.n_elements++;
	
	find_next_free_page_action();
	
	//printf("in eq, before returning. n_el=%d\n",bs_queue.n_elements);
	return 0;
}

int dequeue_bs(struct page_action *pa){
	// If there is something in the queue...
	//printf("in deq. n_el=%d\n",bs_queue.n_elements);
	if(bs_queue.n_elements == 0) return -1;
	struct page_action *head = bs_queue.head;
	
	if(head->next){
		bs_queue.head = head->next;
	} else {
		bs_queue.head = bs_queue.tail = NULL;
	}
	*pa = *head;
	//pa->next = NULL;
	
	reset_page_action(head);
	
	bs_queue.n_elements -= 1;	
	find_next_free_page_action();
	//printf("in deq, before returning. n_el=%d\n",bs_queue.n_elements);
	return 0;	
}

int handle_page_fault(struct process *page_table_id, int page_id){
  int result;
  int free_spot = -1;
  int free_spot_bs = -1;
  int source;
  struct page_desc* page = page_table_id->pt.head;
  struct page_desc* temp = page;//keep track of the head
  //struct page_action action;
  
  int free_space_in_q = BS_Q_SIZE - bs_queue.n_elements;
  
  while(page != NULL && page->page_id != page_id)
  {
  	page = page->next;
  }
  
  if(page == NULL) return -1;//page does not exist
  //check that page is not in memory
  if(page->state == PG_INMEM || page->state == PG_FAULTED)
  {
    return -2;//page is already in memory or faulted
  }
  
  //if page is not in memory, look for a free spot to put it
  free_spot = find_next_free_main();
  
  //if there is no free space in memory, we swap
  if(free_spot < 0)
  {
    /*
    while(temp != NULL && temp->state != PG_INMEM)
    {
      temp = temp->next;
    }
    */
    //temp = lru_list.head;
    temp = pop_from_lru();
    
    if(temp == NULL)
      return -3;//no lru??? this is bad
      
    if(temp->state != PG_INMEM){
    	printf("KERNEL BUG: A page in LRU list that is not in mem!\n");
    	return -3;
    }

    if(free_space_in_q < 2)
      return -4;//queue is too full
    
    // Find a free spot in the bs.
    if(find_next_free_bs() == -1){
    	// There is no free space in the BS either. Memory is really full.
    	return -5;
    }
    page->state = PG_FAULTED;
    source = page->offset;
    page->offset = -1;
    temp->state = PG_SWAPPING;
    enqueue_bs(PA_STORE, temp, temp->offset, next_free_bs);
    enqueue_bs(PA_RETRIEVE, page, source, temp->offset);
    return 1; // not an error but to indicate that we swapped out something
    
  }
  //if there is a free space in memory, we simply queue the copy
  else
  {
  	if(page->state == PG_SWAPPED) source = page->offset;
  	else source = -1;
    page->state = PG_FAULTED;
    page->offset = -1;
    pages_main[free_spot] = page;
    result = enqueue_bs(PA_RETRIEVE, page, source, free_spot);
    if(result < 0)
      return -4;//the queue is full
    
  }
  
  return 0;
}

// bs_interrupt simulates the effect of disk finishing a task and letting the
// kernel know about it. We assume that the finished job is the one in front
// of the page_actions queue.
int bs_interrupt(){
  int result;
  //int free_bs_space;
	struct page_action pa;
	
	result = dequeue_bs(&pa);
	if(result != 0)
	  return -1;//nothing in queue
	  
	switch(pa.op)
	{
	  case PA_NONE:
	  	return -1;
	    break;
	  case PA_STORE:  
	    //pages_main[pa.subject->offset] = NULL;
	    pages_main[pa.source_offset] = NULL;
	    pa.subject->state = PG_SWAPPED;
	    pa.subject->offset = pa.target_offset;
	    pages_bs[pa.target_offset] = pa.subject;
	    // Since we stored this page, we remove it from the lru list. NOT
	    // update: we already removed it when it was the LRU.
    	//remove_from_lru(pa.subject);
	    return 1;
	  case PA_RETRIEVE:
	    
	    if(pa.subject->state == PG_SWAPPED)
  	    //pages_bs[pa.subject->offset] = NULL;
  	    pages_bs[pa.source_offset] = NULL;
  	  
  	  //lru is not considered for kernel process
  	  if(pa.subject->owner->pid != 0)
  	  {
  	  	// Since we just retrieved something into the main mem, now it is
  	  	// the most recently used page.
			  append_to_lru(pa.subject);
    	}
	    
	    pa.subject->state = PG_INMEM;
	    pa.subject->offset = pa.target_offset;
	    pages_main[pa.target_offset] = pa.subject;
	    if(pa.source_offset != -1) pages_bs[pa.source_offset] = NULL;
	    return 2;
	}
}


void init_main(){
 int i;
  // Clear the mem
//  for(i = 0; i < MAIN_SIZE; i++)
//    mem_main[i] = 0;
  for(i = 0; i < MAIN_PAGES; i++) pages_main[i] = NULL;
  next_free_main = MAIN_PAGES - 1;
  return;
}

void init_bs(){
 int i;
//  for(i = 0; i < BS_SIZE; i++)
//    mem_bs[i] = 0;
  for(i = 0; i < BS_PAGES; i++) pages_bs[i] = NULL;
  next_free_bs = BS_PAGES - 1;
  return;
}

// Initialize the main memory and the swap space.
// In the real world, this should probe the hardware and allocate enough space
// in the main memory to manage all memory related data structures. In this
// implementation, assumption is that main memory is 1024kb and the backing
// storage (BS) is 50000kb. Page size is fixed at 4kb (see include.mm.h).
int init_mm(){
  int i;
  init_main();
  init_bs();
  for(i = 0; i < N_PAGES; i++) reset_page(&pages[i]);
  next_free_page = N_PAGES - 1;
  bs_queue.next_free = 0;
  bs_queue.n_elements = 0;
  bs_queue.head = NULL;
  bs_queue.tail = NULL;
  for(i = 0; i < BS_Q_SIZE; i++)
  	reset_page_action(&bs_queue.page_actions[i]);
  	
	lru_list.head = lru_list.tail = NULL;
  return 0;
}

int get_mm_size(){
	int out = 0;
	out += sizeof(struct page_desc) * N_PAGES;
	out += sizeof(struct page_desc*) * N_PAGES;
	out += sizeof(struct bs_queue_definition);
	return out;
}


struct page_desc* get_page(struct process* p, int pg_id)
{
  struct page_desc* desc = p->pt.head;
  while(desc != NULL)
  {
    if(desc->page_id == pg_id)
      return desc;
    else
      desc = desc->next;
  }
  return NULL;
}

int use_page(struct process* proc, int page_id)
{
  struct page_desc* page;

  if(proc == NULL || proc->pid == 0)
    return -1;// process doesn't exist
    
  page = get_page(proc, page_id);
  
  if(page == NULL)
    return -2;// page doesn't exist
  
  if(page->state != PG_INMEM)
  	return -3; // Page is not in memory. It first needs a fault
  
  remove_from_lru(page);
  append_to_lru(page);
  
  return 0;
}











